
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeMap;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/30
 * \* Time: 19:55
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 二叉树的最小深度 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int minDepth(TreeNode root) {
        //如果树本身为空直接返回0
        if(root==null){
            return 0;
        }

        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        //root本身就是一层，所depth初始化为1
        int depth=1;

        while (!q.isEmpty()){
            int sz=q.size();
            //将当前队列中的所有节点向四周扩散
            for(int i=0;i<sz;i++){
                TreeNode cur=q.poll();
                //判断是否到达终点（也就是叶子节点）
                if(cur.left==null&&cur.right==null){
                    return depth;
                }
                //将cur的相邻节点加入队列
                if(cur.left!=null){
                    q.offer(cur.left);
                }
                if(cur.right!=null){
                    q.offer(cur.right);
                }
            }
            //弄完一层，depth+1
            depth++;
        }
        //最后一层弄完，说明是满二叉树
        return depth;
    }
}